/*
 *
 *
 *wait-for graph to check deadlock
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 * */
#define _GNU_SOURCE
#include <dlfcn.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define ENABLE_GRAPH	1

#if ENABLE_GRAPH
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>

typedef unsigned long int uint64;
#define MAX		100
enum Type { PROCESS, RESOURCE };

struct source_type {
	uint64 id;
	enum Type type;
	uint64 lock_id;
	int degress;
};

struct vertex {
	struct source_type s;
	struct vertex *next;
};

struct task_graph {
	struct vertex list[MAX];
	int num;
	struct source_type locklist[MAX];
	int lockidx;
	pthread_mutex_t mutex;
};

struct task_graph *tg = NULL;
int path[MAX + 1];
int visited[MAX];
int k = 0;
int deadlock = 0;

struct vertex *create_vertex(struct source_type type) {
	struct vertex *tex = (struct vertex *)malloc(sizeof(struct vertex));
	tex->s = type;
	tex->next = NULL;
	return tex;
}

int search_vertex(struct source_type type) {
	int i = 0;
	for (i = 0; i < tg->num; i++) {
		if (tg->list[i].s.type == type.type && tg->list[i].s.id == type.id) {
			return i;
		}
	}
	return -1;
}

void add_vertex(struct source_type type) {
	if (search_vertex(type) == -1) {
		tg->list[tg->num].s = type;
		tg->list[tg->num].next = NULL;
		tg->num++;
	}
}

int add_edge(struct source_type from, struct source_type to) {
	add_vertex(from);
	add_vertex(to);
	struct vertex *v = &(tg->list[search_vertex(from)]);
	while (v->next != NULL) {
		v = v->next;
	}

	v->next = create_vertex(to);
}

int verify_edge(struct source_type i, struct source_type j) {
	if (tg->num == 0) return 0;
	int idx = search_vertex(i);
	if (idx == -1) {
		return 0;
	}

	struct vertex *v = &(tg->list[idx]);
	while (v != NULL) {
		if (v->s.id == j.id) return 1;
		v = v->next;
	}
	return 0;
}

int remove_edge(struct source_type from, struct source_type to) {
	int idxi = search_vertex(from);
	int idxj = search_vertex(to);
	if (idxi != -1 && idxj != -1) {
		struct vertex *v = &tg->list[idxi];
		struct vertex *remove;
		while (v->next != NULL) {
			if (v->next->s.id == to.id) {
				remove = v->next;
				v->next = v->next->next;
				free(remove);
				break;
			}
			v = v->next;
		}
	}
}

void print_deadlock(void) {
	int i = 0;
	printf("deadlock : ");
	for (i = 0; i < k - 1; i++) {
		printf("%ld --> ", tg->list[path[i]].s.id);
	}

	printf("%ld\n", tg->list[path[i]].s.id);
}

int DFS(int idx) {
	struct vertex *ver = &tg->list[idx];
	if (visited[idx] == 1) {
		path[k++] = idx;
		print_deadlock();
		deadlock = 1;
		return 0;
	}
	visited[idx] = 1;
	path[k++] = idx;
	while (ver->next != NULL) {
		DFS(search_vertex(ver->next->s));
		k--;
		ver = ver->next;
	}
	return 1;
}

int search_for_cycle(int idx) {
	struct vertex *ver = &tg->list[idx];
	visited[idx] = 1;
	k = 0;
	path[k++] = idx;
	while (ver->next != NULL) {
		int i = 0;
		for (i = 0; i < tg->num; i++) {
			if (i == idx) continue;
			visited[i] = 0;
		}

		for (i = 1; i <= MAX; i++) {
			path[i] = -1;
		}
		k = 1;
		DFS(search_vertex(ver->next->s));
		ver = ver->next;
	}
}
#endif

int search_lock(uint64 lock) {
	int i = 0;
	for (i = 0; i < tg->lockidx; i++) {
		if (tg->locklist[i].lock_id == lock) {
			return i;
		}
	}
	return -1;
}

int search_empty_lock(uint64 lock) {
	int i = 0;
	for (i = 0; i < tg->lockidx; i++) {
		if (tg->locklist[i].lock_id == 0) {
			return i;
		}
	}
	return tg->lockidx;
}

int inc(int *value, int add) {
	int old;
	__asm__ volatile("lock;xaddl %2, %1;": "=a"(old): "m"(*value), "a" (add): "cc", "memory");
	return old;
}

void lock_before(uint64 thread_id, uint64 lockaddr) {
	int idx = 0;// list<threadid, toThreadid>
	for (idx = 0; idx < tg->lockidx; idx++) {
		if ((tg->locklist[idx].lock_id == lockaddr)) { 
			// 如果锁已存在
			#if 1
			struct source_type from;
			from.id = thread_id;
			from.type = PROCESS;
			add_vertex(from);	
			// 添加节点
			struct source_type to;
			to.id = tg->locklist[idx].id;
			tg->locklist[idx].degress++; // 统计抢锁的用户
			to.type = PROCESS;
			add_vertex(to);
			if (!verify_edge(from, to)) {
				// 如果边不存在
				add_edge(from, to); // 则加边
			}
			#else
			struct source_type from;
			from.id = thread_id;
			from.type = PROCESS;
			struct source_type to;
			to.id = tg->locklist[idx].id;
			tg->locklist[idx].degress++;
			to.type = PROCESS;
			add_edge(from, to); // 加边
			#endif
		}
	}
}

void lock_after(uint64 thread_id, uint64 lockaddr) {
	int idx = 0;
	if (-1 == (idx = search_lock(lockaddr))) {  
	// 锁不存在，lock list opera /*添加新的节点*/
	int eidx = search_empty_lock(lockaddr);
	tg->locklist[eidx].id = thread_id;
	tg->locklist[eidx].lock_id = lockaddr;
	inc(&tg->lockidx, 1);//原子操作
	}else {
		/* 当A调用lock时，B已占用，就建立了边，当B释放锁并且A抢到锁，需要把之前加的边移除*/
		struct source_type from;
		from.id = thread_id;
		from.type = PROCESS;
		struct source_type to;
		to.id = tg->locklist[idx].id;
		tg->locklist[idx].degress--;
		to.type = PROCESS;
		if (verify_edge(from, to)) //如果边存在
			remove_edge(from, to); // 则移除
		tg->locklist[idx].id = thread_id;
	}
}

void unlock_after(uint64 thread_id, uint64 lockaddr) {
	int idx = search_lock(lockaddr);
	if (tg->locklist[idx].degress == 0) {
		//用户数为0才删除节点
		tg->locklist[idx].id = 0;
		tg->locklist[idx].lock_id = 0;
		//inc(&tg->lockidx, -1);
	}
}

/********************* 检测死锁 start ***************************/
void check_dead_lock(void) {
	int i = 0;
	deadlock = 0;
	for (i = 0; i < tg->num; i++) {
		if (deadlock == 1) break;
		search_for_cycle(i);
	}

	if (deadlock == 0) {
		printf("no deadlock\n");
	}
}

static void *thread_routine(void *args) {
	while (1) {
		sleep(5);
		check_dead_lock();
	}
}

void start_check(void) {
	tg = (struct task_graph*)malloc(sizeof(struct task_graph));
	tg->num = 0;
	tg->lockidx = 0;
	pthread_t tid;
	pthread_create(&tid, NULL, thread_routine, NULL);
}
/********************* 检测死锁 end ***************************/

/********************* hook start ***************************/
typedef int(*pthread_mutex_lock_t)(pthread_mutex_t *mutex);
typedef int(*pthread_mutex_unlock_t)(pthread_mutex_t *mutex);
pthread_mutex_lock_t	pthread_mutex_lock_f;
pthread_mutex_unlock_t	pthread_mutex_unlock_f;
int pthread_mutex_lock(pthread_mutex_t *mutex){
	pthread_t selfid = pthread_self();
	#if ENABLE_GRAPH
		lock_before(selfid, (uint64)mutex);
		pthread_mutex_lock_f(mutex);
		lock_after(selfid, (uint64)mutex);
	#else
		pthread_mutex_lock_f(mutex);
	#endif
	printf("pthread_mutex_lock: %ld, %p\n", selfid, mutex);
	return 0;
}

int pthread_mutex_unlock(pthread_mutex_t *mutex){
	pthread_t selfid = pthread_self();
	pthread_mutex_unlock_f(mutex);
	#if ENABLE_GRAPH
		unlock_after(selfid, (uint64)mutex);
	#endif
		printf("pthread_mutex_unlock: %ld, %p\n", selfid, mutex);
		return 0;
}

int init_hook(){
	pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");
	pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");
	return 0;
}
/********************* hook end ***************************/
#if 1 // debug
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;

void *thread_funcA(void *arg){
	pthread_mutex_lock(&mutex1);
	sleep(1);
	pthread_mutex_lock(&mutex2);
	printf("funcA --> \n");
	pthread_mutex_unlock(&mutex2);
	pthread_mutex_unlock(&mutex1);
}

void *thread_funcB(void *arg){
	pthread_mutex_lock(&mutex2);
	sleep(1);
	pthread_mutex_lock(&mutex3);
	printf("funcB --> \n");
	pthread_mutex_unlock(&mutex3);
	pthread_mutex_unlock(&mutex2);
}

void *thread_funcC(void *arg){
	pthread_mutex_lock(&mutex3);
	sleep(1);
	pthread_mutex_lock(&mutex4);
	printf("funcC --> \n");
	pthread_mutex_unlock(&mutex4);
	pthread_mutex_unlock(&mutex3);
}

void *thread_funcD(void *arg){
	pthread_mutex_lock(&mutex4);
	sleep(1);
	pthread_mutex_lock(&mutex1);
	printf("funcD --> \n");
	pthread_mutex_unlock(&mutex1);
	pthread_mutex_unlock(&mutex4);
}

int main(){
	init_hook();
	#if ENABLE_GRAPH
		start_check();
		printf("start check dead lock.\n");
	#endif
		pthread_t tid[4] = { 0 };
		pthread_create(&tid[0], NULL, thread_funcA, NULL);
		pthread_create(&tid[1], NULL, thread_funcB, NULL);
		pthread_create(&tid[2], NULL, thread_funcC, NULL);
		pthread_create(&tid[3], NULL, thread_funcD, NULL);
		pthread_join(tid[0], NULL);
		pthread_join(tid[1], NULL);
		pthread_join(tid[2], NULL);
		pthread_join(tid[3], NULL);
		return 0;
}
#endif
